package 回溯;
//https://leetcode.cn/problems/island-perimeter/
public class 岛屿的周长 {
    //BFS辅助处理
    int[] x = new int[]{1 , -1 , 0 , 0};
    int[] y = new int[]{0 , 0 , 1 , -1};
    public int islandPerimeter(int[][] grid) {
        for (int i = 0 ; i < grid.length ; i++){
            for (int j = 0 ; j < grid[0].length ; j++){
                if (grid[i][j] == 1){
                    return fun_DFS(grid , i , j);
                }
            }
        }
        return 0;
        //return fun_BFS(grid);
    }
    public int fun_DFS(int[][] grid , int gx , int gy){
        //这道题的目的是计算边长边长边长不是岛屿
        if (gx < 0 || gx >= grid.length || gy < 0 || gy >= grid[0].length){
            //当前岛屿不符合要求，说明岛屿这边空了不用递归了，给他的边长加一
            return 1;
        }
        if (grid[gx][gy] == 0){
            //岛屿这边是海洋，不符合条件，不用递归了，给岛屿边长加一
            return 1;
        }
        if (grid[gx][gy] != 1){
            //这个已经判断过了，他的上下左右边长都已经经过处理了直接返回
            return 0;
        }
        grid[gx][gy] = 2;
        return fun_DFS(grid , gx - 1 , gy) + fun_DFS(grid , gx + 1 , gy) + fun_DFS(grid , gx , gy - 1) + fun_DFS(grid , gx , gy + 1);
    }

    public int fun_BFS(int[][] grid){
        //BFS在遍历时只会找其周围四个格子的情况，不用考虑重复，每次循环遇到陆地就遍历其周围四个方向
        int real = 0;
        for (int i = 0 ; i < grid.length ; i++){
            for (int j = 0 ; j < grid[0].length ; j++){
                if (grid[i][j] == 1){
                    int num = 0;
                    for (int k = 0; k < 4; k++) {
                        int m = i + x[k];
                        int n = j + y[k];
                        if (m < 0 || m >= grid.length || n < 0 || n >= grid[0].length || grid[m][n] == 0){
                            num += 1;
                        }
                    }
                    real += num;
                }
            }
        }
        return real;
    }
}
